package graphquerying.reachability;

import java.util.HashMap;

/**
 * Thej GRIL-index manager
 * Main class of reachability querying functions
 * @author BaiJian
 */
public class GRILIndexManager {
	private static int rank = Interval.START_RANK;
	private static final int INTERVAL_SIZE = 3;
	
	/**
	 * Mapped from R-Graph's id to its GRILIndex
	 */
	private static HashMap<String, GRILIndex> indexMapping = new HashMap<String, GRILIndex>();
	
	/**
	 * Construct index for the input R-Graph
	 * Using randomized labeling algorithm
	 * If the R-Graph's index is constructed before, it will not do this again
	 * 
	 * @param rGraph The input R-Graph
	 */
	public static void constructIndex(RGraph rGraph) {
		System.out.println("Check index of rGraph with id=" + rGraph.getId());
		if (!hasIndex(rGraph.getId())) {
			System.out.println("No corresponding index is existed. Constructing index now, please wait...");
			long startTime = System.currentTimeMillis();
			GRILIndex gIndex = new GRILIndex();
			//Initialize index
			for (String rNodeId : rGraph.getNodesIdList()) {
				Interval intervals[] = new Interval[INTERVAL_SIZE];
				for (int i = 0; i < intervals.length; i++) {
					intervals[i] = new Interval();
				}
				gIndex.getIntervalMapping().put(rNodeId, intervals);
			}
			//Start post-order DFS
			for (int i = 0; i < INTERVAL_SIZE; i++) {
				rank = Interval.START_RANK;
				rGraph.initialNodesVisitedStatus();
				//Visit roots randomly
				int randomRoots[] = generateRandomSequence(rGraph.getRootsIdList().size());
				for (int rootIndex : randomRoots) {
					randomizedVisit(rGraph.getRootsIdList().get(rootIndex), i, rGraph, gIndex);
				}
			}
			indexMapping.put(rGraph.getId(), gIndex);
			System.out.println("Done. Time cost: " + (System.currentTimeMillis() - startTime) + "ms");
		}
	}
	
	/**
	 * Randomly visit the children of the node
	 * @param rNodeId The current R-node id
	 * @param index The interval array index
	 * @param rGraph The R-graph the node belongs to
	 * @param gIndex The GRIL-Index to be created
	 */
	private static void randomizedVisit(String rNodeId, int index, RGraph rGraph, GRILIndex gIndex) {
		RNode rNode = rGraph.getNodesMap().get(rNodeId);
		if (rNode.getStatus() == VisitedStatus.NOT_VISITED) {
			rNode.setStatus(VisitedStatus.BEING_VISITED);
			int randomChildren[] = generateRandomSequence(rNode.getAdjRNodes().size());
			for (int childIndex : randomChildren) {
				//Run DFS recursively
				randomizedVisit(rNode.getAdjRNodes().get(childIndex), index, rGraph, gIndex);
			}
			//Set the rank itselves
			gIndex.getIntervalMapping().get(rNodeId)[index].setSelfRank(rank);
			int minRank = rank;
			//Find the minimal rank of its children
			for (String childId : rNode.getAdjRNodes()) {
				if (minRank > gIndex.getIntervalMapping().get(childId)[index].getLowestRank()) {
					minRank = gIndex.getIntervalMapping().get(childId)[index].getLowestRank();
				}
			}
			gIndex.getIntervalMapping().get(rNodeId)[index].setLowestRank(minRank);
			rNode.setStatus(VisitedStatus.FINISHED);
			rank++;
		}
	}
	
	/**
	 * Shuffle the sequence
	 * @param size The sequence from <i>0</i> to <i>size-1</i>
	 * 
	 * @return The shuffled sequence
	 */
	private static int[] generateRandomSequence(int size) {
		int result[] = new int[size];
		for (int i = 0; i < size; i++) {
			result[i] = i;
		}
		for (int i = 0; i < size; i++) {
			int cIndex = (int)(Math.random() * (i + 1));
			int temp = result[cIndex];
			result[cIndex] = result[i];
			result[i] = temp;
		}
		return result;
	}
	
	/**
	 * Test whether the node with <b>startNodeId</b> can reach to the node with <b>endNodeId</b>
	 * @param rGraph The generated rGraph
	 * @param startNodeId The source node's id of the source graph
	 * @param endNodeId The destination node's id of the source graph
	 * 
	 * @return <code>true</code> if it's reachable. Otherwise <code>false</code>
	 */
	public static boolean isReachable(RGraph rGraph, String startNodeId, String endNodeId) {
		String startRNodeId = rGraph.getIdMap().get(startNodeId);
		String endRNodeId = rGraph.getIdMap().get(endNodeId);
		boolean isReachable = true;
		if (startRNodeId.equals(endRNodeId)) {
			isReachable = true;
		} else {
			isReachable = prunnedDFS(rGraph, startRNodeId, endRNodeId);
		}
		return isReachable;
	}
	
	/**
	 * Test whether the R-node with <b>startRNodeId</b> can reach to the R-node with <b>endRNodeId</b>
	 * <p>Running DFS with prunning</p>
	 * @param rGraph The generated rGraph
	 * @param startRNodeId The source R-node's id of <b>rGraph</b>
	 * @param endRNodeId The destination R-node's id of <b>rGraph</b>
	 * 
	 * @return <code>true</code> if it's reachable. Otherwise <code>false</code>
	 */
	private static boolean prunnedDFS(RGraph rGraph, String startRNodeId, String endRNodeId) {
		if (startRNodeId.equals(endRNodeId)) {
			return true;
		}
		GRILIndex gIndex = indexMapping.get(rGraph.getId());
		if (isAllIntervalsContained(gIndex, endRNodeId, startRNodeId)) {
			for (String childRNodeId : rGraph.getNodesMap().get(startRNodeId).getAdjRNodes()) {
				if (prunnedDFS(rGraph, childRNodeId, endRNodeId)) {
					return true;
				}
			}
		}
		return false;
	}
	
	/**
	 * Test whether the intervals of <b>subRNodeId</b> are <i>all</i> contained by those of <b>superRNodeId</b>
	 * <p>Running DFS with prunning</p>
	 * @param gIndex The corresponding GRIL-index
	 * @param subRNodeId The tested contained intervals' R-node id
	 * @param superRNodeId The tested containing intervals' R-node id
	 * 
	 * @return <code>true</code> if the intervals of <b>subRNodeId</b> are <i>all</i> contained by those of <b>superRNodeId</b>.
	 * Otherwise <code>false</code>
	 */
	private static boolean isAllIntervalsContained(GRILIndex gIndex, String subRNodeId, String superRNodeId) {
		Interval superRNodeIntervals[] = gIndex.getIntervalMapping().get(superRNodeId);
		Interval subRNodeIntervals[] = gIndex.getIntervalMapping().get(subRNodeId);
		boolean result = true;
		//If Lu does not contain Lv, return false immediately
		for (int i = 0; i < INTERVAL_SIZE; i++) {
			if (!subRNodeIntervals[i].isContainedBy(superRNodeIntervals[i])) {
				result = false;
				break;
			}
		}
		return result;
	}
	
	/**
	 * Check whether the rGraph has been indexed
	 * @param rGraphId The identifier of the graph
	 * 
	 * @return <code>true</code> if its indices has been constructed. Otherwise <code>false</code>
	 */
	public static boolean hasIndex(String rGraphId) {
		return indexMapping.containsKey(rGraphId);
	}
}
